#include "..\include\RedBlackData.h"

void RedBlackData::push(int key, int value)
{
	RedBlackNode* node = this->createNode(key, value);

	RedBlackNode* root = this->getRoot();

	if (!root)
	{
		this->setRoot(node);
	}
	else
	{
		while (1) {
			/*if (key == root->key) {
				
				root->value = value;
				delete node;
				return;

			} else */if (root->key < key) {
				if (nullptr == root->right) {
					root->right = node;
					break;
				}
				else {
					root = root->right;
				}
			}
			else {
				if (nullptr == root->left) {
					root->left = node;
					break;
				}
				else {
					root = root->left;
				}
			}
		}
		node->parent = root;
	}

	this->insetCaseOne(node);
}


bool RedBlackData::delNode(int key)
{

	RedBlackNode* root = this->getRoot();

	if (nullptr == root)
	{
		return false;
	}

	RedBlackNode* findNode = this->findNode(key);

	if (nullptr == findNode)
	{
		return false;
	}

	/// <summary>
	///		
	/// 		9B 
	///		  /    \
	///		 6R    15B
	///     /   \   /  \
	///    3B  8B 11R  18R
	///   /  \
	///  1R  4R
	/// 比如删除4该怎么办 
	
	/// 节点有两个子节点 符合 c 和 f
	if ( findNode->left && findNode->right)
	{
		RedBlackNode* node = this->findTheLowestRightNode(findNode->left);

		// 把找到的右节点 赋给要删除的节点
		findNode->key = node->key;
		
		findNode->value = node->value;

		// findeNode 变成了左子树中右节点的最低节点 指针所指向的数据已经不是我们要删除的节点了
		findNode = node;
	}
	// 左子树中右节点的最低节点是否存在节点
	RedBlackNode* child = findNode->right ? findNode->right : findNode->left;


	if (Color::BLACK == this->getNodeColor(findNode))
	{
		findNode->color = this->getNodeColor(child);

		this->deleteCaseOne(findNode);
	}

	// 把自己替换成自己的孩子字节点
	this->replaceNode(findNode, child);

	// 如果是根节点 那边新上任的根节点必须变为黑色
	if (nullptr == findNode->parent && nullptr != child)
	{
		child->color = Color::BLACK;
	}

	// 删除
	delete findNode;

	return true;
}
